The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Interactive computer graphics is the subclass of computer graphics in which a user dynamically controls the picture's content, format, size or color on a display surface by means of an interaction device such as a keyboard, lever or joystick. see Fundamentals of Interactive Computer Graphics, by J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc., in the computer's memory) is the usual domain of interactive computer graphics. This is in contrast to the creation of images of real objects, which come directly or indirectly from a scanning device of some sort, e.g., a film scanner, TV scanner, ultrasound scanner, etc.
There are two primary classes of interactive computer graphics systems: random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. (As explained below, the data is stored in a frame buffer or refresh buffer.) In the random-scan display system, the component points of each successive output primitive are stored sequentially in memory and are plotted in that order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan display system, the refresh memory is arranged as a 2-dimensional array of data. The entry or value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. By convention, the location of each display element is specified by a unique (X,Y) coordinate. Z conventionally represents the depth ordinate.
Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel, short for the image processing term "picture element." Hereinafter, to avoid confusion, the term "display pixel" will be used to indicate picture elements of a display device, and "storage pixel" to indicate memory locations corresponding to the display pixels.
FIG. 1 is a simplified block diagram of a typical prior art raster-scan graphic system. Such a system includes an image creation system 12, an image storage system 14 (such as a refresh buffer or frame buffer), an image display system 16, a raster display 18 and an interaction device 20. The image creation system 12 converts output primitives into the data stored in the refresh buffer or frame buffer of the image storage system 14. The instruction set processing speed of the image creation system 12 establishes most of the characteristics of the raster-scan system 10. Moreover, the image creation system 12 is particularly malleable because it is typically implemented with a microprocessor. See Chapter 12 of Fundamentals of Interactive Computer Graphics, referenced above.
The overall speed with which all or part of the image storage data can be changed is dependent upon:
(i) how fast the application program operates; PA0 (ii) how fast the computer prepares instructions to the display; PA0 (ii) how fast the instructions are conveyed to the display; and PA0 (iv) how fast the image creation system executes instructions.
It is the last process (the image creation system's execution of instructions) which is often the slowest, because the scan conversion algorithm typically requires many iterations. Usually the faster this process, the faster the overall system response time to user commands. Moreover, it is well known that response time is critical to user satisfaction.
There is a fundamental mismatch between the two dimensional array of pixel values used to drive a raster-scan display and the lines, points, and areas used to represent images by the image creation system 12. The process of converting a line, point, and area representation to the pixel data array of the image storage system 14 is called "scan conversion." Such scan conversion algorithms are universally needed in an interactive raster-scan graphics system, and are usually incorporated into the image creation system 12.
The scan conversion algorithm used in a raster-scan graphics system will be invoked quite often, typically hundreds or even thousandths of times each time an image is created or modified. Hence, it must not only create visually satisfactory images, but must also execute as rapidly as possible. Indeed speed versus image quality is the basic tradeoff in selecting a scan conversion algorithm. Some are fast and give jagged edges, while others are slower but give smoother edges. However, it can generally be said that faster is better for a given image quality.
FIG. 2 depicts an exemplary line, y =mx +b, along with a vector 22 as it might be rendered (i.e., stored) in the frame buffer of the image storage system 14 (and thus displayed on the display 18). (It should be noted that the term "render" is used herein to refer to the process of storing pixel data in the frame buffer and /or displaying data stored in the frame buffer on the display device.) Vector 22 is composed of a set of display and corresponding storage pixels P.sub.0, P.sub.1, P.sub.2, . . . P.sub.N. The vector is rendered by stepping along the major axis, in this case the X-axis, and computing the corresponding minor axis (Y-axis) ordinate values. These (X,Y) coordinates define the storage and display pixels composing the vector 22. The basic task of a scan conversion algorithm for lines is to compute the integer coordinates of the display pixels lying nearest the line.
As can be seen from vector 22 depicted in FIG. 2, the limited resolution of the frame buffer 14 and display 18 causes the vector to become jagged, or "aliased." Techniques for generating antialiased (i.e., smooth) vectors are known in the art. See, for example, Chapter 11.2.3 of Fundamentals of Interactive Computer Graphics, referenced above, and references cited therein for details of known antialiasing techniques. These known antialiasing techniques however, while producing visually acceptable images, are too slow for many applications. The object of the present invention is therefore to provide an efficient and rapid method and apparatus for rendering antialiased vectors.